import java.util.ArrayDeque;
import java.util.Deque;

public class LongestValidParentheses {
    // 最长的括号子串
    // https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=295&tqId=1375406&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int longestValidParentheses (String s) {
        // write code here
        int left = 0, right = 0;
        int maxLength = 0;
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            char ch = c[i];
            if (ch == '(') {
                left++;
            } else {
                right++;
            }
            // 如果左右括号的数量是相等的，那么就需要统计一下有效括号的长度
            if (left == right) {
                maxLength = Math.max(maxLength, right * 2);
            } else if (right > left) {
                // 如果右括号的数量大于左括号的数量，那么此时构成的子串的括号就是不匹配的
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = c.length-1; i >= 0; i--) {
            char ch = c[i];
            if (ch == ')') {
                right++;
            } else {
                left++;
            }
            if (left == right) {
                maxLength = Math.max(maxLength, left * 2);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxLength;
    }

    public int longestValidParentheses1 (String s) {
        // write code here
        // 使用栈，在栈中存放最近的一个未匹配的括号的下标
        Deque<Integer> stack = new ArrayDeque<>();
        stack.add(-1);
        char[] c = s.toCharArray();
        int maxLength = 0;
        for (int i = 0; i < c.length; i++) {
            char ch = c[i];
            if (ch == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLength = Math.max(maxLength, i-stack.peek());
                }
            }
        }
        return maxLength;
    }
}
